- Title
- A new approach to the feasibility pump in mixed integer programming
- Creator
- Boland, Natashia; Eberhard, A.C.; Engineer, F.; Tsoukalas, A.
- Relation
- SIAM Journal on Optimization Vol. 22, Issue 3, p. 831-861
- Publisher Link
- http://dx.doi.org/10.1137/110823596
- Publisher
- Society for Industrial and Applied Mathematics (SIAM)
- Resource Type
- journal article
- Date
- 2012
- Description
- The feasibility pump is a recent, highly successful heuristic for general mixed integer linear programming problems. We show that the feasibility pump heuristic can be interpreted as a discrete version of the proximal point algorithm. In doing so, we extend and generalize some of the fundamental results in this area to provide new supporting theory. We show that feasibility pump algorithms implicitly minimize a weighted combination of the objective and a term which penalizes lack of integrality. This function has many local minima, some of which correspond to feasible integral solutions; the feasibility pump’s use of random restarts can be viewed as seeking to escape these local minima when they are not feasible integral solutions. This interpretation suggests alternative ways of incorporating restarts, one of which is the application of cutting planes. Numerical experiments with cutting planes show encouraging results on standard test libraries.
- Subject
- feasibility pump; proximal points; Moreau regularization; integer programming; cutting planes
- Identifier
- http://hdl.handle.net/1959.13/939360
- Identifier
- uon:12786
- Identifier
- ISSN:1052-6234
- Language
- eng
- Full Text
- Reviewed
- Hits: 2719
- Visitors: 3984
- Downloads: 856
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 642 KB | Adobe Acrobat PDF | View Details Download |